package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了18.85%的用户
内存消耗：2.1 MB, 在所有 Go 提交中击败了16.75%的用户
 */
func removeDuplicateLetters(s string) string {

	res := ""
	ins := map[byte]bool{}

	last := map[byte]int{}
	for i := 0; i < len(s); i++ { last[s[i]] = i }

	for i := 0; i < len(s); i++ {
		if ins[s[i]] { continue }
		for len(res) > 0 && res[len(res) - 1] > s[i] && last[res[len(res) - 1]] > i {
			ins[res[len(res) - 1]] = false
			res = res[:len(res) - 1]
		}
		res += string(s[i])
		ins[s[i]] = true
	}
	return res
}

func main() {

	fmt.Println(removeDuplicateLetters("a"))  // a
	fmt.Println(removeDuplicateLetters("cbacdcbc"))  // acdb
}
